/*
 * @lc app=leetcode.cn id=70 lang=cpp
 *
 * [70] 爬楼梯
 */

// @lc code=start
class Solution
{
public:
    int climbStairs(int n)
    {
        if (n <= 3)
        {
            return n;
        }
        int p = 1, q = 2, res = 3;
        for (size_t i = 3; i < n; i++)
        // 滚动数组动态规划与含备忘录的递归相比，使用了更少了空间，只保存有效的两个解，而不是把之前的都保存了
        {
            p = q;
            q = res;
            res = p + q;
        }
        return res;
    }
};
/*
这样写更简便
    int p = 0, q = 0, r = 1;
    for (int i = 1; i <= n; ++i)
    {
        p = q;
        q = r;
        r = p + q;
    }
    return r;
还有使用线性代数矩阵幂的骚方法，之后做
*/
// @lc code=end
